package slidingwindow

import (
	"container/list"
	"math"
)

func AllTimesMinToMax(arr []int32) int {
	ans := math.MinInt32
	size := len(arr)

	for i:=0; i<size; i++ {
		for j:=i; j<size; j++ {
			var sum int32
			min := math.MaxInt32
			for k:=i; k<=j; k++ {
				sum += arr[k]
				min = Min(int32(min), arr[k])
			}
			ans = Max(int32(ans), sum*int32(min))
		}
	}
	return ans
}

func Min(a, b int32) int {
	if a > b {
		return int(b)
	}
	return int(a)
}

func Max(a, b int32) int {
	if a > b {
		return int(a)
	}
	return int(b)
}


func MaxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func MinInt(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func AllTimesMinToMax1(arr []int) int {

	ans := math.MinInt32
	size := len(arr)
	sumArr := make([]int, size)
	for i:=0; i<size; i++ {
		if i == 0 {
			sumArr[i] = arr[i]
		} else {
			sumArr[i] = sumArr[i-1] + arr[i]
		}

	}
	monotStack := list.New()
	for i:=0; i<size; i++ {
		// 当栈的最上面一个数大于要进来的数时，需要弹出，并记录左右边界值
		for monotStack.Len() > 0 && arr[monotStack.Back().Value.([]int)[0]] > arr[i] {
			curPopIndexArr := monotStack.Remove(monotStack.Back()).([]int)
			leftLess := -1
			for _, v := range curPopIndexArr {
				curPopIndex := v
				if monotStack.Len() > 0 {
					lastArr := monotStack.Back().Value.([]int)
					leftLess = lastArr[len(lastArr)-1]
				}
				// 计算结果
				min := arr[curPopIndex]
				var leftStart int
				rightEnd := i-1
				if leftLess == -1 {
					leftStart = curPopIndex - 1
				} else {
					leftStart = leftLess
				}
				sum := 0
				if leftLess == -1 {
					sum = sumArr[rightEnd]
				} else {
					sum = sumArr[rightEnd] - sumArr[leftStart]
				}
				ans = MaxInt(ans, sum*min)
			}
		}
		// 当遇到相等的时候, 需要加入顶层的arr
		if monotStack.Len() > 0 && arr[monotStack.Back().Value.([]int)[0]] == arr[i] {
			curPopIndexArr := monotStack.Remove(monotStack.Back()).([]int)
			monotStack.PushBack(append(curPopIndexArr, i))
		} else {
			monotStack.PushBack([]int{i})
		}
	}

	for  monotStack.Len() > 0 {
		curPopIndexArr := monotStack.Remove(monotStack.Back()).([]int)
		leftLess := -1
		for _, v := range curPopIndexArr {
			curPopIndex := v
			if monotStack.Len() > 0 {
				lastArr := monotStack.Back().Value.([]int)
				leftLess = lastArr[len(lastArr)-1]
			}
			// 计算结果
			min := arr[curPopIndex]
			leftStart := leftLess
			if leftLess == -1 {
				leftStart = curPopIndex - 1
			}
			rightEnd := size-1
			sum := 0
			if leftLess == -1 {
				sum = sumArr[rightEnd]
			} else {
				sum = sumArr[rightEnd] - sumArr[leftStart]
			}
			ans = MaxInt(ans, sum*min)
		}
	}
	return ans
}